#Rem
	Header: - Fast Object List component
#End
Strict

#Rem
summary: TFastList

T = user object/item

#End
Class TFastList<T>

	
	Field _head:TFastCell<T> = null
	Field _tail:TFastCell<T> = null

	#Rem
	summary: Add object to List
	#End	
	Method Add:Void( item:T )
		AddFirst(item)
	End

	#Rem
	summary: Remove first iten from list and return removed item
	#End	
	Method Pop:T()
		Return RemoveFirst()
	End
	
	#Rem
	summary: compare two objects
	#End	
	Method Equals:Bool( lhs:Object,rhs:Object )
		Return lhs=rhs
	End
	
	#Rem
	summary: clear object list
	#End	
	Method Clear:Void()
		_head=null
		_tail=null
	End

	#Rem
	summary: get items count 
	#End	
	Method Count:Int()
		Local n:Int = 0
		Local node:TFastCell<T>=Self._head
		While node<>null
			node=node.nextItem
			n+=1
		Wend
		Return n
	End
	
	#Rem
	summary: Is list empty?
	#End	
	Method IsEmpty:Bool()
		Return _head = null
	End
	
	#Rem
	summary: Return first cell node
	#End	
	Method FirstNode:TFastCell<T>()
		Return _head
	End
	#Rem
	summary: Return first items 
	#End	
	Method First:T()
		If( _head <> null )
			Return _head.elt
		End
		Return null
	End

	#Rem
	summary: return last item
	#End	
	Method Last:T()
		If( _tail <> null )
			Return _tail.elt
		End
		Return null
	End
	
	#Rem
	summary: add at first position Cell and return incserted cell node
	#End	
	Method AddFirst:TFastCell<T>( data:T )
		Local added := New TFastCell<T>( _head,null,data )
		_head = added
		If( _tail = null )
			_tail = added
		End
		Return added
	End

	#Rem
	summary: add at end Cell and return incserted cell node
	#End	
	Method AddLast:TFastCell<T>( data:T )
		Local added := New TFastCell<T>( null,_tail,data )
		_tail = added
		If( _head = null )
			_head = added
		End
		Return added
	End

	#Rem
	summary: remove item from list
	#End	
	Method Remove : Bool ( value:T )
		Return RemoveFirst(value)
	End
	
	#Rem
	summary: remove first item, return true when was removed, else false
	#End	
	Method RemoveFirst : Bool( value:T )
		Local node:=_head
		While node<>null
			If Equals( node.elt,value ) 
				Remove(node)
				Return True
			End
			node=node.nextItem
		Wend
		Return False
	End

	#Rem
	summary: remove each equals items 
	value:T -  item to remove
	#End	
	Method RemoveEach:Void( value:T )
		Local node:=_head
		While node<>null
			Local nextnode:=node.nextItem
			If Equals( node.elt,value ) 
				Remove(node)
			End
			node = nextNode
		Wend
	End

	#Rem
	summary: remove first item when isn't list empty and return removed item
	#End	
	Method RemoveFirst:T()
		If( IsEmpty() )
			Return null
		End
		Local data:T=_head.elt
		Remove(_head)
		Return data
	End

	#Rem
	summary: remove first item when isn't list empty
	#End	
	Method RemoveLast:T()
		If( IsEmpty() )
			Return null
		End
		Local data:T=_tail.elt
		Remove(_tail)
		Return data
	End

	#Rem
	summary: remove cell node from list
	#End	
	Method Remove:Void(cell:TFastCell<T>)
		If( cell = _tail )
			_tail = cell._pred
		End
		If( cell = _head )
			_head = cell.nextItem
		End
		If( cell.nextItem <> null )
			cell.nextItem._pred=cell._pred
		End
		If( cell._pred <> null )	
			cell._pred.nextItem=cell.nextItem
		End
	End
	
	#Rem
	summary: Object enumerator
	#End	
	Method ObjectEnumerator:TEnumerator<T>()
		Return New TEnumerator<T>( Self )
	End
	
	
End

#Rem
summary: TFastCell 
#End	
Class TFastCell<T>

	'create a _head node
	Method New()
		nextItem=null
		_pred=null
	End

	#Rem
	summary: 
	#End	
	Method New( data:T, succ:TFastCell<T>)
		nextItem=succ
		_pred=succ._pred
		If( nextItem <> null )
			nextItem._pred=Self
		End
		If( _pred <> null )
			_pred.nextItem=Self
		End
		elt=data
	End

	'create a link node
	#Rem
	summary: 
	#End	
	Method New( succ:TFastCell<T>,pred:TFastCell<T>,data:T )
		nextItem=succ
		_pred=pred
		If( nextItem <> null )
			nextItem._pred=Self
		End
		If( _pred <> null )
			_pred.nextItem=Self
		End
		elt=data
	End
	
	#Rem
	summary: 
	#End	
	Method Value:T()
		Return elt
	End

	#Rem
	summary: 
	#End	
	Field elt:T
	
	#Rem
	summary: 
	#End	
	Field nextItem:TFastCell<T>

Private

	Field _pred:TFastCell<T>

End

#Rem
summary: TEnumerator
#End	
Class TEnumerator<T>

	#Rem
	summary: 
	#End	
	Method New( list:TFastList<T> )
		_list=list
		_curr=list._head
	End Method

	#Rem
	summary: 
	#End	
	Method HasNext:Bool()
		Return _curr<>null
	End 

	#Rem
	summary: 
	#End	
	Method NextObject:T()
		Local data:T=_curr.elt
		_curr=_curr.nextItem
		Return data
	End

Private
	
	Field _list:TFastList<T>
	Field _curr:TFastCell<T>

End

#Rem
Footer: Comapre FastList<T> with standard Monkey List<T>

[code]
	Field fList:TFastList<TVector2>
	Field sList:List<TVector2>
	
	Field start_time:Int
	' START when app is created
	Method Start:Void()
		Self.fList = New TFastList<TVector2>()
		Self.sList = New List<TVector2>()
		
		Self.start_time = Millisecs()
		
		Print("Create Fast Object List")		
		For Local i:Int = 0 To 10000
			Self.fList.Add(New TVector2(i,i))
		Next
		Print("End: "+(Millisecs()-Self.start_time)+" ms")
		
		Self.start_time = Millisecs()
		Print("Create Object List")
		For Local i:Int = 0 To 10000
			Self.sList.AddLast(New TVector2(i,i))
		Next
		Print("End: "+(Millisecs()-Self.start_time)+" ms")
		
		
		Print("READ From Fast List with EachIn loop ")
		Self.start_time = Millisecs()		
		For Local itm:TVector2 = EachIn Self.fList
			Local v:TVector2 = itm
		Next
		Print("End: "+(Millisecs()-Self.start_time)+" ms")
		
		Print("READ From Fast List with While loop ")
		Self.start_time = Millisecs()		
		Local itm  := Self.fList.FirstNode()				
		While( Not( itm = null ) ) 				
			' little bit slow		
			' Local v:TVector2 = itm.Value()			
			' very quisk
			Local v:TVector2 = itm.elt
			itm = itm.nextItem			
		Wend
		Print("End: "+(Millisecs()-Self.start_time)+" ms")
		
		Print("READ From List")
		Self.start_time = Millisecs()
		For Local itm:TVector2 = EachIn Self.sList
			Local v:TVector2 = itm
		Next
		Print("End: "+(Millisecs()-Self.start_time)+" ms")
		
	End
[/code]

Result:
[code]
Create Fast Object List
End: 24 ms
Create Object List
End: 25 ms
READ From Fast List with EachIn loop 
End: 5 ms
READ From Fast List with While loop 
End: 1 ms
READ From List
End: 4 ms
[/code]
#End
